package baseclass.d_list;

import java.util.HashMap;
import java.util.Map;

/**
 *  rand指针是SpecNode类中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向null。
 *  请实现一个函数完成这个链表中所有结构的复制，并返回复制的新链表的头节点。
 *
 *   要求1，额外空间复杂度o(n)：
 *  		利用hashMap，key存原节点，value存新拷贝的节点。
 *  		遍历的时候串起来，注意get(node)得到的就是node的复制的节点;
 *  		get(node).next = get(node.next); //就是把node的复制的节点 指向 node.next的复制的节点
 *  		get(node).random = get(node.random); // 就是把node的复制节点的random  指向  node.random的复制节点
 *   要求2，额外空间复杂度o(1):
 *  		同copyList中，把没给节点拷贝一个新节点放在原节点的后面。
 *  		第一次遍历 ，新节点的random串起来， cur.next.random = cur.random.next ;
 *  		第二次遍历，分离
 * @date 2020/2/28 18:19
 */
class RandomListNode {
    int label;
    RandomListNode next;
    RandomListNode random;

    RandomListNode(int data) {
        this.label = data;
    }
}

public class Code06_CopyWithRandom {

    public static RandomListNode copyListWithRand1(RandomListNode head) {
        if(head == null) return head;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode p = head;
        //拷贝所有节点
        while (p != null){
            map.put(p,new RandomListNode(p.label));
            p = p.next;
        }
        //串新的节点
        p = head;
        RandomListNode p2 = map.get(head);
        while (p != null){
            p2.next = map.get(p.next);
            p2.random = map.get(p.random);
            p2 = p2.next;
            p = p.next;
        }
        return map.get(head);
    }

    public static RandomListNode copyListWithRand2(RandomListNode head) {
        if (head == null) return head;
        RandomListNode p = head;
        //对每个节点拷贝，拷贝节点放在该节点后面
        while (p != null){
            RandomListNode next = p.next;
            RandomListNode copy = new RandomListNode(p.label);
            p.next = copy;
            copy.next = next;
            p = next;
        }
        p = head;
        //为每个拷贝节点的random赋值
        while (p != null){
            RandomListNode copy = p.next;
            RandomListNode next = copy.next;
            copy.random = p.random == null ? null : p.random.next;
            p = next;
        }

        //进行分离
        p = head;
        RandomListNode newHead = new RandomListNode(-1);
        RandomListNode p2  = newHead;
        while (p != null){
            //记录下一个原始节点
            RandomListNode next = p.next.next;
            //找出拷贝节点的next
            RandomListNode copyNext = p.next;
            //进行连接
            p2.next =  copyNext;
            p2 = p2.next;
            p.next = next;
            p = next;
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        RandomListNode head = null;
        RandomListNode res1 = null;
        RandomListNode res2 = null;
       /* printRandLinkedList(head);
        res1 = copyListWithRand1(head);
        printRandLinkedList(res1);
        res2 = copyListWithRand2(head);
        printRandLinkedList(res2);
        printRandLinkedList(head);
        System.out.println("=========================");*/

        head = new RandomListNode(1);
        head.next = new RandomListNode(2);
        head.next.next = new RandomListNode(3);
        head.next.next.next = new RandomListNode(4);
        head.next.next.next.next = new RandomListNode(5);
        head.next.next.next.next.next = new RandomListNode(6);

        head.random = head.next.next.next.next.next; // 1 -> 6
        head.next.random = head.next.next.next.next.next; // 2 -> 6
        head.next.next.random = head.next.next.next.next; // 3 -> 5
        head.next.next.next.random = head.next.next; // 4 -> 3
        head.next.next.next.next.random = null; // 5 -> null
        head.next.next.next.next.next.random = head.next.next.next; // 6 -> 4

        printRandLinkedList(head);
        res1 = copyListWithRand1(head);
        printRandLinkedList(res1);
        System.out.println("============");
        printRandLinkedList(head);
        res2 = copyListWithRand2(head);
        printRandLinkedList(res2);


        System.out.println("=========================");

    }

    private static void printRandLinkedList(RandomListNode head) {
        RandomListNode cur = head;
        System.out.print("order: ");
        while (cur != null) {
            System.out.print(cur.label + " ");
            cur = cur.next;
        }
        System.out.println();
        cur = head;
        System.out.print("random:  ");
        while (cur != null) {
            System.out.print(cur.random == null ? "- " : cur.random.label + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}
